#include <iostream>
using namespace std;


int merge(int *a, int start,int mid, int end,int *temp)
{
	int i=mid;
	int j=end;
	int k=end;
    int count=0;
	while(i>=start&&j>mid)
	{
		if (a[i]>a[j])
		{
			temp[k--]=a[i--];
			count+=j-mid;
		}
		else
		{
			temp[k--]=a[j--];
		}
	}
	while(i>=start)
	{
		temp[k--]=a[i--];
	}
	while(j>mid)
	{
		temp[k--]=a[j--];
	} 
	for (int m=end;m>k;m--)
	{
	   a[m]=temp[m];
	}
	return count;
}
int find(int *a, int start, int end, int *temp)
{
	int count=0;
	if (start<end)
	{
		int mid=(start+end)/2;
		count+=find(a,start,mid,temp);
		count+=find(a,mid+1,end,temp);
		count+=merge(a,start,mid,end,temp);
	}
	return count;
}

int main()
{
	int arry[]={1,3,7,8,2,4,6,5};
	int len=sizeof(arry)/sizeof(arry[0]);
	int *temp=new int[len];
	memset(temp,0,len);
	int count=find(arry,0,len-1,temp);
	cout<<count<<endl;
	cout<<endl;
	//for (int i=0;i<len;i++)
	//{
	//	cout<<arry[i]<<" ";
	//}
	//int x=0x7FFFFFFF;
 //   int y=0x80000000;
	//cout<<x<<endl;
	//cout<<y<<endl;
	//int a[3]={0,1,2};

	return 0;
}